package com.kongge.algorithm.demo;

import com.kongge.algorithm.list.ListNode;

/**
 * 输入一个链表，输出该链表中倒数第K和结点
 * @author gaoshiqi
 *
 */
public class FindKthNodeToTail implements IAlgorithm{

	public void execute() {
		ListNode<Integer> head = ListNode.createList(1, 2, 3, 4, 5);
		int k = 0;
		
		ListNode<Integer> kNode = findNodeToTail(head, k);
		if (kNode != null) {			
			System.out.println("倒数第 " + k + " 个结点，值为 " + kNode.t);
		} else {
			System.out.println("倒数第 " + k + " 个结点不存在 ");
		}
	}

	private ListNode<Integer> findNodeToTail(ListNode<Integer> head, int k) {
		if (head == null || k <= 0) {
			return null;
		}
		ListNode<Integer> kNode = null;
		ListNode<Integer> tempNode = head;
		int count = k - 1;
		while (tempNode.next != null) {
			tempNode = tempNode.next;
			if (count == 0) {
				kNode = tempNode;
			} else if (count > 1) {
				count --;
			} else {
				if (kNode == null) {
					kNode = head;
				} else {
					kNode = kNode.next;
				}
			}
		}
		return kNode;
	}
}
